1. Field of the Invention
The present invention relates generally to an apparatus and method for network communication, and more particularly to network node arrangements that gather information regarding neighboring nodes and distribute the information regarding. the neighbors throughout the network.
2. Related Art
In xe2x80x9cad hocxe2x80x9d networks, as opposed to conventional networks, a given node typically finds itself with xe2x80x9cpotential neighborxe2x80x9d nodes with which it can directly communicate, but which are not predefined or currently linked with the node. The given node also finds itself with xe2x80x9cactual neighborxe2x80x9d nodes, which are predefined or currently linked with the given node. With conventional technology, each node forms neighbor relationships with every such potential neighbor node by promoting the potential neighbor node to an actual neighbor node. This promotion scheme is explained with reference to FIG. 2A. As shown in FIG. 2A, reference letters A-E represent network gateway nodes (e.g., network access points). A network xe2x80x9cbackbonexe2x80x9d is formed through gateway links. Reference letters a-g represent member nodes, which gain network access through a gateway. As illustrated, members a-d gain network access through gateway A. Similarly, members e-g gain network access through gateway E.
As illustrated, node A has an actual neighbor gateway link with each of nodes C and E. The dashed lines between nodes A and B, and between nodes A and D indicate potential neighbor relationships. Under current routing protocols, each node forms neighbor relationships with each such potential neighbor node by promoting the potential neighbor node to an actual neighbor node. Under current protocols, node A will necessarily promote nodes B and D to be actual (or xe2x80x9cfullxe2x80x9d) neighbor nodes.
For many routing protocols, however, promoting each potential neighbor into an actual neighbor greatly increases control traffic within the network. The increased traffic can be particularly burdensome in those networks, for example radio-based networks, where bandwidth is at a premium. Describing all existing neighbor relationships and their varying metrics while the links between neighbors change consumes a tremendous amount of the limited bandwidth.
In current network systems, either all potential neighbors are adopted as actual neighbors or a local determination is made (e.g., on the basis of received signal strength) as to which potential neighbor should be adopted as an actual neighbor. However, information on potential neighbors is not distributed throughout conventional networks.
It may be desirable for a given node to form only a subset of possible neighbor relationships, and to advertise only that subset through network traffic. The selection of the subset is difficult, however, and local choices (e.g., when a node selects its own neighbors from a set of potential neighbors only on the basis of locally available information) can cause globally sub-optimal choices. An object of this invention, therefore, is to provide a method and apparatus to distribute some or all of the xe2x80x9cpotential neighborxe2x80x9d information so that nodes in a network can perform globally optimal selections of actual neighbors from potential neighbor sets.
The present invention relates to a distribution of neighbor information through an ad hoc network.
According to the invention, a communication network has plural nodes capable of receiving and issuing messages, each node having neighbor nodes including actual neighboring nodes. Network information is received at a node, from other nodes in the network.
According to one aspect, the present invention relates to generating in a communication node, information of potential neighboring nodes responsive to the received network information from other nodes of the network, and issuing a network information message from the node to the other nodes of the network, which network information message includes information of the potential neighboring nodes.
According to another aspect, the potential neighboring node information includes a node identifier for the node, a node specific sequence number for the node and a list of potential neighbors of the node.
In yet another aspect, the information for each potential neighboring node includes a metric corresponding to a cost of linking the potential neighbor and the node. The information for each potential neighboring node can also include a metric corresponding to a serviceability of a link between the potential neighbor and the node.
Yet another aspect of the present invention is that the network information message which includes the information of potential neighboring nodes is issued from the node less frequently than other network information messages. The network information message of potential neighboring nodes can also be issued in response to an occurrence of a predetermined event. A predetermined event can include at least one of the nodes realizing a change in the potential neighbors, a change in a state of a potential neighboring node, and an occurrence of a predetermined time-period.
In still another aspect, the network information messages of the node are issued to the actual neighboring nodes for reissuance to other nodes of the network.
Yet another aspect includes storing network topology information in the node, processing the received network information messages including the information of potential neighboring nodes to modify the network topology information, and issuing network information messages including the network topology modifying information. The network topology modifying information can include information corresponding to network reconfiguration. The network reconfiguring information can also include at least one of changing potential neighboring nodes to actual neighboring nodes and changing actual nodes to potential neighboring nodes.
According to one embodiment, a method of operating a mobile station for use in a wireless mobile communication network is provided. The network employs a plurality of mobile stations, each of the plurality of stations being capable of transmitting and receiving communication signals. The method includes the steps of: (i) receiving at the mobile station, network information from other stations in the network; (ii) generating in the mobile station, information of potential neighboring stations responsive to the received network information from other stations of the network; and (iii) issuing a network information message from the mobile station to the other stations of the network, which network information message includes information of the potential neighboring stations.
According to another embodiment, a programmable computer for use in operating a communication node in an ad hoc communication network is provided. The communication node is capable of issuing and receiving messages, each node having neighboring nodes including actual neighboring nodes. The programmable computer includes at least one memory including at least one region for storing computer executable program code, and a processor for executing the program code stored in the memory. The program code includes: (i) code to receive at the node, network information from other nodes in the network, (ii) code to generate in the node, information of potential neighboring nodes responsive to the received network information from other nodes of the network, and (iii) code to issue a network information message from the node to the other nodes of the network, which network information message includes information of the potential neighboring nodes.
In another embodiment, a network node apparatus includes a memory, a processor and a transmitter. The memory stores link-state information regarding neighboring nodes in a network. The processor (i) determines a list of potential neighbor nodes, and (ii) determines cost-of-transaction information regarding each node on the list of potential neighbor nodes. The transmitter transmits the list of potential neighbor nodes and the determined cost-of-transaction information to the network.
In still another embodiment, computer executable code stored on a computer readable medium is provided. The code operates a communication node in a communication network having plural nodes capable of receiving and issuing messages, each node having neighboring nodes including actual neighboring nodes. The code includes: (i) code to receive at the node, network information from other nodes in the network; (ii) code to generate in the node, information of potential neighboring nodes responsive to the received network information from other nodes of the network; and (iii) code to issue a network information message from the node to the other nodes of the network, which network information message includes information of the potential neighboring nodes.
In still another embodiment, a network node apparatus includes means for storing, means for determining, and means for transmitting. The storing means stores link-state information regarding neighboring nodes in a network. The determining means determines a list of potential neighbor nodes and cost-of-transaction information regarding each node on the list of potential neighbor nodes. The transmitting means transmits the list of potential neighbor nodes and the determined cost-of-transaction information to the network. These and other objects, features and advantages will be apparent from the following description of the preferred embodiments of the present invention.